/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @see https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  if(!head) {
    return null;
  }
  inner(head, null);

  function inner(header, tail) {
    // 找到链表中间节点
    let slow = header;
    let fast = header;
    while(fast != tail && fast.next != tail) {
      fast = fast.next.next;
      slow = slow.next;
    }
    console.log(fast, slow)
  }
};

var sortedListToBST2 = function (head) {
  if (!head) return null;
  return dfs(head, null);
};

function dfs(head, tail) {
  if (head == tail) return null;
  let fast = head;
  let slow = head;
  while (fast != tail && fast.next != tail) {
    fast = fast.next.next;
    slow = slow.next;
  }
  let root = new TreeNode(slow.val);
  root.left = dfs(head, slow);
  root.right = dfs(slow.next, tail);
  return root;
}

function TreeNode(val, left, right) {
  this.val = val;
  this.left = left || null;
  this.right = right || null;
}

let link2 = {
  val: 5,
  next: {
    val: 0,
    next: {
      val: 1,
      next: {
        val: 8,
        next: {
          val: 4,
          next: {
            val: 5,
            next: {
              val:-10,
              next: {
                val: 11,
                next: {
                  val: 12,
                  next: {
                    val: 13
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
// 5 0 1 8 4 5

console.log(sortedListToBST2(link2))